package labuladong;

import java.util.*;

public class Al01 {
    // 斐波那契数列使用备忘录算法，使用memo数组当作备忘录
    int fib(int n) {
        if (n < 1)
            return 0;
         int[] memo = new int[n + 1];
        Arrays.fill(memo, 0);
        return helper(memo, n);
    }

    int helper(int[] memo, int n) {
        if (n == 1 || n == 2)
            return 1;
        if (memo[n] != 0)
            return memo[n];
        memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
        return memo[n];
    }

    // 凑零钱问题
    int coinChange(int[] coins,   int amount) {
          int[] dp = new int[amount + 1];
        // 当金额是0时，0个金币即可
        for (int i = 0; i < dp.length; i++) {
            dp[i] = i;
        }
        for (int i = 0; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i - coins[j] < 0)
                    continue;
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[amount];
    }

    // 全排列
    /*
     * 回溯算法的框架 result = [] 
     *  def backtrack(路径,选择列表){ 
     *    if 满足条件： result.add(路径) return
     *    for 路径 in 路径列表: 
     *    做选择 backtrack(路径，路径列表) 
     *    撤销选择 
     * }
     */
    List<List<Integer>> res = new ArrayList<>();
    List<List<Integer>> permute(int[] nums) {
          LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, track);
        System.out.println(res);
        return res;
    }

    void backtrack(int[] nums, LinkedList<Integer> track) {
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (track.contains(nums[i]))
                continue;
            track.add(nums[i]);
            backtrack(nums, track);
            track.removeLast();
        }
    }

    // BFS算法，问题的本质就是让你在一幅图中找到从起点start到终点target的最短距离
    // 例如走迷宫，单词编辑
    /* 计算从起点start到终点target的距离
        int BFS(Node start, Node target){
            Queue<Node> q; // 核心数据结构
            Set<Node> visited; // 避免走回头路
            q.offer(start);
            int step = 0;
            while(q not empty){
                int sz = q.size();
                for(int i=0;i<sz;i++){
                    Node cur = q.poll();
                    if(cur == targer){
                        return step;
                    }
                    // 将cur的相邻节点加入到队列中
                    for(Node x : cur.adj()){
                        if(x not visited){
                            q.offer(x);
                            visited.add(x);
                        }
                    }
                }
                step++;
            }
        }
    */
    // 二叉树的最小深度
    int minDepth(  TreeNode root) {
        if (root == null)
            return 0;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        int depth = 0;
        while (!que.isEmpty()) {
              int sz = que.size();
            for (int i = 0; i < sz; i++) {
                  TreeNode tmp = que.poll();
                if (tmp.left == null && tmp.right == null) {
                    return depth;
                }
                if (tmp.left != null) {
                    que.offer(tmp.left);
                }
                if (tmp.right != null) {
                    que.offer(tmp.right);
                }
            }
        }
        return depth;
    }

    // 密码锁问题 
    int openLock(  String[] deadends,   String target) {
          Set<String> deads = new HashSet<>();
        for (  String s : deadends)
            deads.add(s);
          Set<String> visited = new HashSet<>();
          Queue<String> q = new LinkedList<>();
        int step = 0;
        q.offer("0000");
        visited.add("0000");
        while (!q.isEmpty()) {
              int sz = q.size();
            for (int i = 0; i < sz; i++) {
                  String cur = q.poll();
                if (cur.contains(cur))
                    continue;
                if (cur.equals(target))
                    return step;
                for (int j = 0; j < 4; j++) {
                      String up = plusOne(cur, j);
                    if (!visited.contains(up)) {
                        q.offer(up);
                        visited.add(up);
                    }
                      String down = minusOne(cur, j);
                    if (!visited.contains(down)) {
                        q.offer(down);
                        visited.add(down);
                    }
                }
            }
            step++;
        }
        return -1;
    }

    private String minusOne(  String cur,   int j) {
          char[] ch = cur.toCharArray();
        if (ch[j] == '0') {
            ch[j] = '9';
        } else {
            ch[j] -= 1;
        }
        return new String(ch);
    }

    private String plusOne(  String cur,   int j) {
          char[] ch = cur.toCharArray();
        if (ch[j] == '9') {
            ch[j] = '0';
        } else {
            ch[j] += 1;
        }
        return new String(ch);
    }

    /*
     * 零、二分搜索框架 int binarySearch(int[] nums, int target){ int left = 0, right =0 ;
     * while(...){ int mid = left + (right - left) / 2; if(nums[mid] == target){
     * return mid; }else if(nums[mid]>target){ right = mid - 1; }else
     * if(numss[mid]<target){ left = mid + 1; } } return -1; }
     */
    // 搜索一个数
    public int binarySearch(  int[] nums,   int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
              int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }

    // 寻找左侧边界的二分搜索
    int left_bound(  int[] nums,   int target) {
        if (nums.length == 0)
            return -1;
        int left = 0;
        int right = nums.length; // attention
        while (left < right) {
              int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid; // attention
            }
        }
        if (left >= nums.length || nums[left] != target)
            return -1;
        return left;
    }

    /*
     * 滑动窗口问题框架 void slidingWindow(String s, String t){ unordered_map<char, int>
     * need, window; for(char c : t) need[c]++; int left = 0, right = 0; int valid =
     * 0; while(right < s.size()){ // 将字符c移入窗口 char c = s[right]; // 右移窗口 right++;
     * // 进行窗口内的一系列更新 ... // dubug输出的位置 printf("window:[%d, %d]\n",left,right); //
     * 判断左侧窗口是否需要收索 while(window need shrink){ char d = s[left]; left++; ... } } }
     * 
     */
    // 最小覆盖字串问题 https://leetcode-cn.com/problems/minimum-window-substring/
    public String minWindows(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0)
            return "";
          int[] need = new int[128];
          int[] window = new int[128];
        for (Character c : t.toCharArray())
            need[c]++;
        int l = 0;
        int r = 0;
        // 记录当前有多少个字符
        int count = 0;
        String res = "";
        int minLength = s.length() + 1;
        while (r < s.length()) {
              char c = s.charAt(r);
            window[c]++;
            if (need[c] > 0 && need[c] >= window[c])
                count++;
            while (count == t.length()) {
                  char ch = s.charAt(l);
                if (need[ch] > 0 && need[ch] >= window[ch]) {
                    count--;
                }
                if (r - l + 1 < minLength) {
                    minLength = r - l + 1;
                    res = s.substring(l, r + 1);
                }
                window[ch]--;
                l++;
            }
        }
        return res;
    }

    // 字符串的排列 https://leetcode-cn.com/problems/permutation-in-string/
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length())
            return false;
          int[] s1map = new int[26];
          int[] s2map = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            s1map[s1.charAt(i) - 'a']++;
            s2map[s2.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s2.length() - s1.length(); i++) {
            if (matches(s1map, s2map)) {
                return true;
            }
            s2map[s2.charAt(i + s1.length() - 'a')]++;
            s2map[s2.charAt(i) - 'a']--;
        }
        return matches(s1map, s2map);
    }

    public boolean matches(  int[] s1map,   int[] s2map) {
        for (int i = 0; i < 26; i++) {
            if (s1map[i] != s2map[i])
                return false;
        }
        return true;
    }

    // 无重复字符的最长字串
    // https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
    public int lengestOfLongestSubstring(  String s) {
        if(s.length()==0) return 0;
        Map<Character, Integer> map = new HashMap<>();
        int res = 0;
        int left = 0;
        char[] c = s.toCharArray();
        for (int i = 0; i < c.length; i++) {
            if (map.containsKey(c[i])) {
                left = Math.max(left, map.get(c[i])+1) ;
            }
            res = Math.max(res, i-left+1);
            map.put(c[i], i);
        }
        return res;
    }

    //  股票买卖问题
    /* 穷举和状态
        for 状态1 in 状态1的所有取值
            for 状态2 in 状态2的所有取值
                for ...
                    dp[状态1][状态2][] = 择优(选择1，选择2，选择3)
    */
    // k=1
    int maxProfit_k_1(int[] prices){
        int n = prices.length;
        int dp_i_0=0,dp_i_1=Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            dp_i_0=Math.max(dp_i_0, dp_i_1+prices[i]);
            dp_i_1=Math.max(dp_i_1, -prices[i]);
        }
        return dp_i_0;
    }

    // k=+infinity,可以认为k是不会改变的，也就是我们不用再记录k这个状态了
    int maxProfit_k_inf(int[] prices){
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1+prices[i]);
            dp_i_1 = Math.max(dp_i_1, temp-prices[i]);
        }
        return dp_i_0;
    }

    // k=+infinity with cooldown, 每次sell之后需要等待一天才能继续交易
    int maxProfit_with_cool(int[] prices){
        int n = prices.length;
        int dp_i_0 = 0, dp_1_1 = Integer.MIN_VALUE;
        int dp_pre_0 = 0; // 代表 dp[i-2][0];
        for (int i = 0; i < n; i++) {
            int tmp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_1_1+prices[i]);
            dp_1_1 = Math.max(dp_1_1, dp_pre_0-prices[i]);
            dp_pre_0 = tmp;
        }
        return dp_i_0;
    }

    // k=+infinity with fee
    int maxProfit_with_fee(int[] prices, int fee){
        int n = prices.length;
        int dp_i_0 = 0, dp_1_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int tmp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_1_1+prices[i]);
            dp_1_1 = Math.max(dp_1_1, tmp-prices[i]-fee);
        }
        return dp_i_0;
    }

    // k=2,穷举k的不同情况
    int maxProfit_k_2(int[] prices){
        int dp_i10 = 0, dp_i11=Integer.MIN_VALUE;
        int dp_i20 = 0, dp_i21=Integer.MIN_VALUE;
        for(int price : prices){
            dp_i20 = Math.max(dp_i20, dp_i21+price);
            dp_i21 = Math.max(dp_i21, dp_i10-price);
            dp_i10 = Math.max(dp_i10, dp_i11+price);
            dp_i11 = Math.max(dp_i11, -price);
        }
        return dp_i20;
    }

    // k=any Integer, 一次交易由买入和卖出构成，至少两天，有效的限制k应该不超过n/2
    int maxProfit_k_any(int max_k, int[] prices){
        int n = prices.length;
        if(max_k > n/2) return maxProfit_k_inf(prices);
        int[][][] dp = new int[n][max_k+1][2];
        for (int i = 0; i < n; i++) {
            for (int k = max_k; k >= 1; k--) {
                if(i-1==-1){
                    dp[i][k][0] = 0;
                    dp[i][k][1] = Integer.MIN_VALUE;

                }
                dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1]+prices[i]);
                dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i]);
            }
        }
        return dp[n-1][max_k][0];
    }

    // 背包问题，是一个动态规划问题，找准需要穷举的状态
    /* for i in [1..n]:
        for w in [1..w]:
            dp[i][w] = max(dp[i-1][w],dp[w-wi[i-1]]+val[i-1])
     */
    // 01背包问题
    int knapsack(int W, int N, int[] wt, int[] val){
        int[][] dp = new int[N+1][W+1];
        for (int i = 1; i<= N; i++) {
            for (int j = 1; j <= W; j++) {
                if(W-wt[i-1]<0){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-wt[i-1]]+val[i-1]);
                }
            }
        }
        return dp[N][W];
    }

    // 01背包变体问题，将数组分成等值两组，
    boolean canPartition(int[] nums){
        int sum = 0;
        for(int num : nums) sum+=num;
        int n = nums.length;
        if(sum%2!=0) return false;
        sum = sum / 2;
        boolean[][] dp = new boolean[n+1][sum+1];
        // 有i个物品，一定能得到价值为0的组合，即啥都不拿
        for(int i=0;i<=n;i++) dp[i][0] = true;
        for(int i=1;i<=n;i++){
            for (int j = 0; j <= sum; j++) {
                if (j-nums[i-1]<0) {
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j] | dp[i-1][sum-nums[i-1]];
                }
            }
        }
        return dp[n][sum];
    }

    // 完全背包问题，注意状态转移方程
    int change(int amount, int[] coins){
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        for(int i=0;i<=n;i++) dp[i][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                if(j - coins[i-1] < 0){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                }
            }
        }
        return dp[n][amount];
    }

    // 编辑距离
    int minDistance(String s1, String s2){
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if(s1.charAt(i-1)==s2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1];
                else
                    // 在删除，新增，和替换之间做选择
                    dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
            }
        }
        return dp[m][n];
    }

    // 一些贪心算法，计算区间
    // 一个简单的方法就是对区间的end进行排序，把与最先结束区间相交的区间去掉，即可获得答案
    int intervalSchedule(int[][] intvs){
        if(intvs.length==0) return 0;
        Arrays.sort(intvs, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[1]-b[1];
            }
        });
        // 至少有一个
        int count = 1;
        int x_end = intvs[0][1];
        for(int[] intervals : intvs){
            // 找到第一个大于x_end的start
            int start = intervals[0];
            if(start >= x_end){
                count++;
                x_end = intervals[1];
            }
        }
        return count;
    }

    //  通配符匹配问题
    /*  通配符[.]很好解决
        关键问题就是通配符[*]，我们使用动态规划来解决这个问题
        当p[j+1]为*通配符时，，我们分情况讨论：
        1、如果匹配，即s[i]==p[j],那么有两种情况
            1.1 p[j]可能匹配到多个字符，比如s="aaa", p="a*"，那么p[0]通过*匹配3个字符"a"
            1.2 p[j]可能匹配到零个字符，比如s="aa", p="a*aa"， 那么由于后面的字符可以匹配s，所以p[0]匹配0次
        2、如果不匹配，即s[i]!=p[j],只有一种情况
            p[j]只能匹配0次，然后看下一个字符能否和s[i]匹配。比如说s = "aa", p = "b*aa"，此时p[0]只能匹配 0 次
    */
    boolean isMatch(String s, String p){
        int m = s.length();
        int n = p.length();
        boolean[][] f = new boolean[m+1][n+1];
        f[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if(p.charAt(j-1)=='*'){
                    f[i][j] = f[i][j-2];
                    if(matches(s, p, i, j-1)){
                        f[i][j] = f[i][j] || f[i-1][j];
                    }
                }else{
                    if(matches(s, p, i, j)){
                        f[i][j] = f[i-1][j];
                    }
                }
            }
        }
        return f[m][n];
    }

    boolean matches(String s, String p, int i, int j){
        if(i==0) return false;
        if(p.charAt(j-1) == '.') return true;
        return s.charAt(i-1) == p.charAt(j-1);
    }
    // 信封问题，先对宽度进行排序，然后按照最长递增子序列的思路来做
    int maxEnvelopes(int[][] envelopes){
        int n = envelopes.length;
        Arrays.sort(envelopes, new Comparator<int[]>(){
            public int compare(int[] a, int [] b){
                return a[0]==b[0]?b[1]-a[1]:a[0]-b[0];
            }
        });
        int[] height = new int[n];
        for (int i = 0; i < n; i++) {
            height[i] = envelopes[i][1];
        }
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(height[j]<height[i]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                    res = Math.max(res, dp[i]);
                }       
            }
        }
        return res;
    }

    // 前缀和技巧：解决字数组问题
    int subarraySun(int[] nums, int k){
        int n = nums.length;
        HashMap<Integer, Integer> preSum = new HashMap<>();
        preSum.put(0, 1);
        int ans = 0, sum0_i=0;
        for (int i = 0; i < n; i++) {
            sum0_i+=nums[i];
            int sum0_j = sum0_i-k;
            if(preSum.containsKey(sum0_j)){
                ans+=preSum.get(sum0_j);
            }
            preSum.put(sum0_i, preSum.getOrDefault(sum0_i, 0)+1);
            
        }
        return ans;
    }

    // 最长公共子序列
    int longestCommonSubsequence(String s1, String s2){
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i < m+1; i++) {
            for (int j = 1; j < n+1; j++) {
                if(s1.charAt(i-1)==s2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1]+1;
                else
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }   
        }
        return dp[m][n];
    }

    // 跳跃游戏
    boolean canJump(int[] nums){
        int n = nums.length;
        int farthest = 0;
        for (int i = 0; i < n-1; i++) {
            farthest = Math.max(farthest, nums[i]+i);
            if(farthest<i) return false;
        }
        return farthest >= n-1;
    } 
    
    // 跳跃游戏2
    int jump(int[] nums){
        int n = nums.length;
        int end = 0, farthest = 0;
        int jumps = 0;
        for (int i = 0; i < n-1; i++) {
            farthest = Math.max(farthest, nums[i]+i);
            if(end==i){
                jumps++;
                end = farthest;
            }
        }
        return jumps;
    }

    public static void main(  String[] args) {
          Al01 al = new Al01();
        // int[] coins = {1,2,5,10,20,100};
        // int amount = 25;
        // al.coinChange(coins, amount);
          int[] nums = { 1, 2, 2, 3 };
          String s = "pwwkew";
        System.out.println(al.left_bound(nums, 2));
        System.out.println(al.lengestOfLongestSubstring(s));
        
       
    }
}

